1. Field of the Invention
The invention relates to the field of error detection and correction in information handling systems. In particular, the invention relates to the reduction of miscorrections in error detection and correction schemes used in digital information systems and employs Fire codes verified by cyclical redundancy coding.
2. Prior Art
The concept of communication, in general, implies that the receiver of information derive the same meaning therefrom as the sender had when he transmitted his message. Achieving communication vis-a-vis individuals is itself often a difficult task. When communication is by way of radio transmission, long line transmission, or even the short distance spanned by an interface device between two pieces of electronic equipment, the communication problem is often complicated by the presence of noise.
The ability to communicate is enhanced when the information is transmitted by means of binary code. Such a code typically consists of two energy states, a high level and a low level state, often referred to as logical states "1" and "0" respectively. Here again, however, noise or equipment faults may cause the receipt of a 1 or a 0 when a 0 or a 1 has been transmitted.
A binary coded word or number will consist of a grouping of 1's and 0's. For example, the code grouping 101 may be taken to represent the quantity five. If an error is introduced in transmission, the code group may be received as the binary code 100, that is, the quantity four. The code group 101 is said to comprise a 3-bit word.
One of the earliest techniques of error detection consisted of the addition of an extra bit to the word transmitted for the sole purpose of checking the received word to determine whether there had been an error in transmission. A bit added to a word to provide such an error check is hereinafter referred to as a check bit. The early technique referred to was known as a parity check. By parity, it was meant that all words transmitted contained an equal number of 1's. In the case referred to as "even parity", all transmitted words contain an even number of 1's. Odd parity implies that all transmitted words contain an odd number of 1's. Thus, the quantity five, in even parity, would be transmitted as 1010, the right-most 0 being the parity check bit. If an error in transmission resulted in the receipt of the word 1000, the parity check would indicate an odd number of 1's and cause a request to b made for the retransmission of the data, it having been recognized that an error existed because the received word lacked even parity. The application of odd parity checks should be apparent to the reader.
While parity checks provide a convenient means for detecting an error in a single bit, the check fails if two bits should be in error. Thus, if the word 1010 is transmitted and the word 0110 is received, the parity check bit will pass the erroneous word with the error undetected. Because of the limitations of the parity check, other, more involved, checking techniques were derived.
The combination of information bits plus check bits is known as a code word. The code word is generated in accordance with a selected polynomial, the polynomial being selected for its ability to meet or exceed the error detection design criterion of the system a characteristic inherent in certain codes provides the descriptor for all such codes. Cyclic Codes. A code is said to be cyclic if any code word, when cycled in either direction, any number of positions, remains a code word of the same code. A code word cycled once implies that the first bit becomes the last bit in the code word and what was originally the second bit becomes the first bit of the new code word. Cycling in the other direction implies that the last bit becomes the first bit in the code word and the next to last bit of the original code word becomes the last bit of the new code word. Because all cyclic codes are linear the sum of two code words results in a code word within the same code.
Cyclic codes were an improvement on the parity check in that multiple-bit errors could now be detected. However, for all practical purposes, cyclic codes, like parity codes, lend themselves merely to the detection of errors in the received information. When an error is detected in the information received, it is necessary that the sender be notified and a retransmission be initiated. To preclude the necessity of retransmitting the data, a self-correcting error detection code was desired.
One of the earlier workers in the field to expound a practical methodology for deriving codes capable of both detecting and correcting errors was R. W. Hamming. (See Hamming, "Error Detecting and Error Correcting Codes" Bell System Tech. J., Vol. 29, 1950, pp. 147-160.) The application of Hamming's work permitted the detection and the correction of randomly occurring errors within a single bit of a received code word. The names of Bose, Ray-Chaudhuri and Hocquenghem became associated with error detecting and correcting codes capable of detecting and correcting errors occurring within multiple bits of a transmitted word. Such codes are familiarly referred to as BCH codes. The designer of an error detection and correction (EDAC) system may choose to use Hamming or BCH codes because of the random nature of the errors encountered and the likelihood that such errors will affect one or more than one bit in any given code word. However, there are other circumstances in which a burst of noise may be expected to adversely affect several bits within a given bit-length. Burst errors are frequently associated with surface defects in disk memories or tape storage devices. So too, atmospheric transmission of data or long-line transfers are subject to noise problems leading to burst errors in the information received. Phillip Fire disclosed the family of cyclic codes which bear his name, and which provide a simple-to-implement burst error detection and correction system. The use of Hamming, BCH, or Fire codes permitted the designer of EDAC systems with the means of correcting errors as they were received and obviated the need to retransmit the information. A significant problem still remained however, the miscorrection of received data.
In general, all of the codes mentioned allow the designer the choice of accurately detecting a greater number of bit errors than the system is capable of correcting. Thus, when the number of bits in error in a code word exceeds the maximum number which are correctable with the code employed, the errors will not be automatically corrected; and, if the number of errors are within the accurate detection capability of the system, a retransmission of the data will be required. However, if the number of errors exceeds the limits of accurate detection, the possibility exists that the system will cause a miscorrection to be made in the received data. With a miscorrection, the tansmitted authorization to pay $100 might have been erroneously received as authority to pay $10,000 and miscorrected to cause the issuance of a $1,000,000 check. As may be readily imagined, such miscorrections may themselves generate a considerable amount of "noise" among managerial staff members.
It is typical of past practice to select a Hamming, BCH, or Fire Code as the main error detection and correction code of the system; to provide each code word with an additional check bit as a parity check to detect errors in the received word; and to select a secondary .-+.Cyclic Redundancy Code (CRC)" to provide enhanced error detection capabilities.
It is seen that the addition of EDAC check bits, cyclic redundancy code check bits, and parity check bits to a given information word directly affect its length and therefore have a direct bearing upon system capabilities. Thus, the length of a code word may determine the speed with which information may be transmitted, and may be determinative of the amount of information which may be stored within a given storage medium. The problem of avoiding a miscorrection has generally been approached by selecting EDAC codes having capabilities of detecting errors beyond the realm of those which are statistically probable in any given system. Enhancing the error detection capabilities of a given system by the selection of a more complex code polynominal tends to increase the complexity of the EDAC encoder and decoder circuitry and to inefficiently increase the length of the code word.
The present invention therefore has as its object the improved efficiency in the utilization of code words used to provide error detection and correction and supplementary detection capabilities. A further object of the invention is to provide a methodology for designing EDAC systems which reduce the probability of making miscorrections to a de minimus level.